<template>
    <div class="demo-collapse">
        <el-collapse v-model="activeNames" @change="handleChange">
            <el-collapse-item title="解题思路" name="thinking">
                <div>
                    <div>
                        1.选择一个起始节点作为最小生成树的起点。
                    </div>
                    <div>
                        2.将该起始节点加入最小生成树集合，并将其标记为已访问。
                    </div>
                    <div>
                        3.在所有与最小生成树集合相邻的边中，选择权重最小的边和它连接的未访问节点。
                    </div>
                    <div>
                        4.将该边和节点加入最小生成树集合，并将该节点标记为已访问。
                    </div>
                    <div>
                        5.重复步骤3和步骤4，直到最小生成树集合包含了图中的所有节点。
                    </div>
                </div>
            </el-collapse-item>
            <el-collapse-item title="代码实现" name="code">
                <!-- <el-image style="width:100%" :src="url" :fit="fit" loading="lazy"></el-image> -->
                <div v-highlight>
                    <div>C/C++:</div>
                    <pre class="language-javascript">
                      <code>
                        #include &lt;stdio.h>
                            #include &lt;iostream>
                            using namespace std;
                            void prim(int mst[100][100], int edgeNum, int verticesNum,int startVertice) {
                                
                                int n = verticesNum;
                            
                                struct node {
                                    int lowCost;
                                }closeEdge[10];
                            
                            
                                for (int v = 0;v  &lt; n;v++) {
                                    closeEdge[v].lowCost = mst[startVertice][v];
                                }
                                closeEdge[startVertice].lowCost = 0;//某节点默认加入生成树
                            
                            
                                int result[100];
                                result[0] = startVertice;
                                printf("%c-",(startVertice+'A'));
                                for (int i = 1;i  &lt;= n - 1;i++) {
                                    int minid = 0;
                                    int minw = 10000;
                                    for (int v = 0;v  &lt;= n - 1;v++)
                                    {
                                        if (closeEdge[v].lowCost > 0 && closeEdge[v].lowCost  &lt; minw)
                                        {
                                            minid = v;
                                            minw = closeEdge[v].lowCost;
                                        }
                                    }
                                    result[i] = minid;
                            
                                    if (i &lt;n-1){
                                        printf("%c-",(minid+'A'));
                                    }
                                    else{
                                        printf("%c",(minid+'A'));
                                    }
                                    closeEdge[minid].lowCost = 0;   //顶点k并入U集 
                                    for (int v = 0;v  &lt;= n - 1;v++) {
                                        if (mst[minid][v]  &lt; closeEdge[v].lowCost) {
                                            closeEdge[v].lowCost = mst[minid][v];
                                        }
                                    }
                                }
                            }
                            int main() {
                                int mst[100][100];
                                int edgeNum = 0;//边数
                                int verticesNum = 0;//节点数
                                int startVertice = 0;//初始节点
                                int weight = 0;
                                char tmp;
                                char x, y;
                                cin >> verticesNum >> edgeNum;
                                for (int i = 0; i  &lt; verticesNum; i++)  //初始化图，所有节点间距离为无穷大
                                    for (int j = 0; j  &lt; verticesNum; j++)
                                        mst[i][j] = 10000;
                                cin >> tmp;
                                startVertice = tmp - 'A';
                                for (int k = 0;k  &lt; edgeNum;k++) {
                                    cin >> x >> y >> weight;
                                    int i = x - 'A', j = y - 'A';  ///ABCDEF
                                    mst[i][j] = weight;
                                    mst[j][i] = weight;
                                }
                                prim(mst, edgeNum, verticesNum, startVertice);
                            }
                            
                      </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Python:</div>
                    <pre class="language-javascript">
                        <code>
                            max = 9999
                            versum, edgesum = map(int, input().split())
                            edge = [[max for o in range(versum+1)] for i in range(versum+1)]  # 记录w 用0记录数据不连通
                            ver = [o for o in range(versum+1)]
                            total_w =0
                            for i in range(edgesum):
                                a, b, data = map(int, input().split())
                                edge[a][b] = data
                                total_w += data
                                edge[b][a] = data
                            class node():  # 数组中元素得类型
                                def __init__(self, ver, w):
                                    self.ver = ver
                                    self.w = w
                            def prim():
                                #u   此为借助得数组，此数组元素表示 ver ->此元素在数组的索引(索引即表示哪一个顶点)，以及之间的权值w，如果为0 的话则表示此顶点已加入到U中
                                #默认以1顶点开始进行查找,也可指定其他的
                                #对数组进行初始化，让数组表示从1 到其它顶点的权值，也就是从U->U-V
                                u = [node(ver[1], edge[1][_]) for _ in range(versum+1)] # _ ==0时无意义，只为了方便索引
                                u[1].w = 0 # 加入到U中
                                s = 0
                                for j in range(versum - 1):  # 寻找足够数量得边
                                    maxx = 9999
                                    for i in range(1,versum+1):  # 寻找数组在中最小w的值，记录此下标
                                        if maxx > u[i].w and u[i].w != 0:  # 0 表示此顶点已加入U
                                            maxx = u[i].w
                                            pos = i
                                    s += u[pos].w #求权值w
                                    u[pos].w = 0 #将顶点加入到U
                                    #对数组进行更新，以表示新加入顶点，到其他顶点的最小的权值
                                    for j in range(1,versum+1):
                                        if edge[pos][j] &lt; u[j].w: #新加入的顶点到其他顶点的w，小于原来顶点到其他顶点的值
                                            u[j].ver = ver[pos]        #更新u 表示新节点到其他节点的(j)w值
                                            u[j].w = edge[pos][j]
                                return s #返回权值记录之和
                            if __name__  =="main":
                                s = prim()
                                print(total_w - s)
                        </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Java:</div>
                    <pre class="language-javascript">
                      <code>
                        package com.xx.prime;

                        public class PrimAlgorithm {
                        
                            public static void main(String[] args) {
                                char[] element = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
                                int nodes = element.length;
                                int[][] side = {
                                        {10000, 5, 7, 10000, 10000, 10000, 2},
                                        {5, 10000, 10000, 9, 10000, 10000, 3},
                                        {7, 10000, 10000, 10000, 8, 10000, 10000},
                                        {10000, 9, 10000, 10000, 10000, 4, 10000},
                                        {10000, 10000, 8, 10000, 10000, 5, 4},
                                        {10000, 10000, 10000, 4, 5, 10000, 6},
                                        {2, 3, 10000, 10000, 4, 6, 10000}};
                        
                                MGraph mGraph = new MGraph(nodes);
                                MinTree minTree = new MinTree();
                                minTree.creatTree(mGraph, nodes, element, side);
                                minTree.showTree(mGraph);
                                minTree.prim(mGraph, 0);
                            }
                        }
                        
                        class MinTree {
                        
                            //创建树
                            public void creatTree(MGraph mGraph, int nodes, char[] element, int[][] side) {
                                for (int i = 0; i &lt; nodes; i++) {
                                    mGraph.element[i] = element[i];
                                    for (int j = 0; j &lt; nodes; j++) {
                                        mGraph.side[i][j] = side[i][j];
                                    }
                                }
                            }
                        
                            //普利姆算法
                            public void prim(MGraph mGraph, int node) {
                                int[] nodes = new int[mGraph.nodes]; //用于标记遍历过的节点
                                 nodes[node] = 1; //将当前节点标记为1 表示已访问
                                //用来记录最小路径两个节点的下标
                                int index1 = -1;
                                int index2 = -1;
                                int minSide = 10000; //遍历与之比较 找到最小的路径
                        
                                for (int k = 1; k &lt; mGraph.nodes; k++) { //若有n个节点 则有n - 1 条边
                                    for (int i = 0; i &lt; mGraph.nodes; i++) {
                                        for (int j = 0; j &lt; mGraph.nodes; j++) {
                                            if (nodes[i] == 1 && nodes[j] == 0 && mGraph.side[i][j] &lt; minSide) {
                                          //      代表在已经访问过的节点中(即本博客上文写到已经加入到Vnew集合中的节点） 遍历 未访问过的节点（即满足条件的节点） 并 找到最小的路径 将其返回
                                                minSide = mGraph.side[i][j]; //最短边上的权值
                                                //最短边的两个顶点
                                                index1 = i;
                                                index2 = j;
                                            }
                                        }
                                    }
                                    //从第内层for循环出来后，表示找到一条最短边
                                    System.out.println("边&lt;" + mGraph.element[index1] + "," + mGraph.element[index2] + ">权值：" + minSide);
                                    nodes[index2] = 1; //将最内层与已访问节点路径最短的节点设置为已访问 （将找出的节点添加到Vnew集合中）
                                    minSide = 10000; //将minSide恢复初始值 开始下次遍历
                                }
                            }
                        
                            //输出树
                            public void showTree(MGraph mGraph) {
                                for (int[] arr : mGraph.side) {
                                    for (int element : arr) {
                                        System.out.print(element + " ");
                                    }
                                    System.out.println();
                                }
                        
                            }
                        }
                        
                        class MGraph {
                            int nodes; //节点的个数
                            char[] element; //节点的元素
                            int[][] side; //存放边，邻接矩阵
                        
                            public MGraph(int nodes) { //构造器
                                this.nodes = nodes;
                                element = new char[nodes];
                                side = new int[nodes][nodes];
                            }
                        }
                        
                           

                      </code>
                    </pre>
                </div>
            </el-collapse-item>
        </el-collapse>
    </div>
</template>

<script lang="ts" setup>
import { ref } from 'vue'
const activeNames = ref(['thinking'])
const handleChange = (val: string[]) => {
    console.log(val)
}
// 代码实现部分
import "vue-code-highlight/themes/prism-solarizedlight.css";
import "vue-code-highlight/themes/window.css";

</script>
